package org.xqh.study.leetcode.algorithm.accountmerge;

import com.alibaba.fastjson.JSONArray;
import org.springframework.util.StopWatch;

import java.util.*;
import java.util.Map.Entry;

/**
 * @ClassName AccountMerge2
 * @Description 按 官方题解 写的 解答 (逻辑一致)
 * https://leetcode-cn.com/problems/accounts-merge/
 * @Author xuqianghui
 * @Date 2021/1/20 11:26
 * @Version 1.0
 */
public class AccountMerge2 {

    public static void main2(String[] args) {
        StopWatch watch = new StopWatch("cost time");
//        String str = ReadTxtFileUtils.readJson(new File("E:\\document\\yzs\\program\\accountMerge.txt"));
        String str = "[[\"Fern\",\"Fern8@m.co\",\"Fern9@m.co\"],[\"Fern\",\"Fern7@m.co\",\"Fern8@m.co\"],[\"Fern\",\"Fern4@m.co\",\"Fern5@m.co\"],[\"Fern\",\"Fern10@m.co\",\"Fern11@m.co\"],[\"Fern\",\"Fern9@m.co\",\"Fern10@m.co\"],[\"Fern\",\"Fern6@m.co\",\"Fern7@m.co\"],[\"Fern\",\"Fern1@m.co\",\"Fern2@m.co\"],[\"Fern\",\"Fern11@m.co\",\"Fern12@m.co\"],[\"Fern\",\"Fern3@m.co\",\"Fern4@m.co\"],[\"Fern\",\"Fern2@m.co\",\"Fern3@m.co\"],[\"Fern\",\"Fern5@m.co\",\"Fern6@m.co\"],[\"Fern\",\"Fern0@m.co\",\"Fern1@m.co\"]]";
        List<List> tmp = JSONArray.parseArray(str, List.class);
        List<List<String>> list = new ArrayList<>();
        for(List l:tmp){
            list.add(l);
        }
        watch.start("merge account");
        accountsMerge(list);
        watch.stop();

        AccountMerge3 merge3 = new AccountMerge3();
        watch.start("merge account 3");
        merge3.accountsMerge(list);
        watch.stop();


//        System.out.println(JSON.toJSONString(accountsMerge(list)));
        System.out.println(watch.prettyPrint());
    }

    public static List<List<String>> accountsMerge(List<List<String>> accounts) {
        int emailCount = 0;//总共邮箱个数
        Map<String, String> emailNameMap = new HashMap<>();//邮箱 和 账户名称 映射
        Map<String, Integer> emailIdxMap = new HashMap<>();//邮箱 和 邮箱 编号(序号) 映射
        for(List<String> items : accounts){
            String name = items.get(0);
            for(int i = 1; i < items.size(); i ++){
                String email = items.get(i);
                if(!emailNameMap.containsKey(email)){
                    emailNameMap.put(email, name);
                    emailIdxMap.put(email, emailCount ++);//邮箱编号
                }
            }
        }

        //合并 并查集
        UnionModel union = new UnionModel(emailCount);
        for(List<String> items : accounts){
            String firstEmail = items.get(1);
            Integer idx1 = emailIdxMap.get(firstEmail);
            for(int i = 2; i < items.size(); i ++){
                Integer idx2 = emailIdxMap.get(items.get(i));
                union.union(idx1, idx2);
            }
        }

        List<List<String>> result = new ArrayList<>();
        Map<Integer, List<String>> retMap = new HashMap<>();
        for(Entry<String, Integer> entry : emailIdxMap.entrySet()){
            Integer curRootIdx = union.find(entry.getValue());//找到 对应编号 邮箱的 根节点邮箱 序号
            List<String> items = retMap.getOrDefault(curRootIdx, new ArrayList<>());
            items.add(entry.getKey());
            retMap.put(curRootIdx, items);
        }
        for(Entry<Integer, List<String>> entry:retMap.entrySet()){
            List<String> items = entry.getValue();
            Collections.sort(items);
            //获取 账号名称
            String accountName = emailNameMap.get(items.get(0));
            List<String> merge = new ArrayList<>();
            merge.add(accountName);
            merge.addAll(items);
            result.add(merge);
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            int m = in.nextInt();
            int n = in.nextInt();
            int[][] arr = new int[n+1][3];
            for(int i = 0; i < arr.length; i ++){
                if(i == 0){
                    int[] first = {m, n};
                    arr[i] = first;
                }else {
                    arr[i][0] = in.nextInt();
                    arr[i][1] = in.nextInt();
                    arr[i][2] = in.nextInt();
                }
            }
            System.out.println(findRefCount(arr));
        }
    }

    public static int findRefCount(int[][] input){
        UnionModel union = new UnionModel(input[0][0]);
        for(int j = 1; j < input.length; j ++){
            int[] relation = input[j];//关系组 三位
            if(relation[2] == 1){
                //是同乡  合并
                union.union(relation[0] - 1, relation[1] - 1);
            }
        }
        int count = 0;
        for(int i = 1; i < union.getParent().length; i++){
            if(union.find(i) == union.find(0)){
                count ++;
            }
        }
        return count;
    }

    public static class UnionModel{
        private int[] parent;//每个email 父节点序号

        public int[] getParent() {
            return parent;
        }

        public UnionModel(int len){
            //初始化 父节点 均为自身
            parent = new int[len];
            for(int i = 0;i < len; i++){
                parent[i] = i;
            }
        }

        /**
         * 并查集 合并
         * @param idx1
         * @param idx2
         */
        public void union(int idx1, int idx2){
            parent[find(idx2)] = find(idx1);
        }

        /**
         * 找对应 序号的 根节点 序号
         * @param idx
         * @return
         */
        public int find(int idx){
            if(parent[idx] != idx){//判断 是否是 根节点
                parent[idx] = find(parent[idx]);
            }
            return parent[idx];
        }
    }
}
